1. Field of the Invention
The present invention relates to real-time image encoding systems, and more particularly, to a method and apparatus for estimating a motion using a hierarchical search approach, and an image encoding system using the method and apparatus.
2. Description of the Related Art
Among all elements of a general image encoder, a motion estimator performs the most intensive calculations. A fast motion estimation algorithm can reduce a number of calculations performed in the motion estimator. Also, the fast motion estimation algorithm can execute a computation faster than a full search block matching algorithm without degradation in performance. A solution for fast motion estimation is a hierarchical search approach.
If the hierarchical search approach is applied to MPEG-2 encoders, a frame motion estimation and a field motion estimation must be performed on all level of images into which a frame image is divided.
FIG. 1 is a conceptual diagram illustrating the hierarchical search approach applied to a conventional MPEG-2 encoder. Referring to FIG. 1, a current frame and a reference (or previous) frame form a hierarchical structure through subsampling. In a three-stage hierarchical search approach, the current and reference frames each includes a lowest resolution level (level 2) image 110, an intermediate resolution level (level 1) image 120, and a highest resolution level (level 0) image 130.
Hierarchical motion estimation on the hierarchical frame structure begins by initiating a full search on the level 2 image 110 and obtaining initial search points with a minimum Sum of Absolute Differences (SADs). Next, local searches are performed on the level 1 image 120 based on the initial search points obtained from the level 2 image 110. New initial search points with the minimum SADs are extracted by the local searches performed on the level 1 image 120. Thereafter, the local searches are performed on the level 0 image 130 based on the new initial search points obtained from the level 1 image 120. Consequently, the local searches on the level 0 image 130 obtain final motion vectors.
Hence, when the MPEG-2 encoder processes prediction frames (P-frames), five hierarchical searches are performed on frames and fields, that is, between frames, on top to top (Top2Top) fields, on top to bottom (Top2Bot) fields, on bottom to top (Bot2Top) fields, and on bottom to bottom (Bot2Bot) fields. When the MPEG-2 encoder processes bidirectional frames (B-frames), a total of 10 hierarchical searches are performed on the B-frames by including forward and backward searches. Accordingly, during the motion estimation in the MPEG-2 encoder, an application of such hierarchical motion searches requires extra memory for use upon both frame and field motion estimations, and demands intensive computation.